# strs = ['abcrgreg','abcfkefefe','abcetwrtwe']
# #  找出公共前缀
# strss = ['qwekjhgf','qwekjhnbgvf','qweokng']
# def func(strs):
#     if not strs:
#         return ""
#
#     strs.sort()
#     first = strs[0]
#     last = strs[-1]
#     i = 0
#
#     while i <len(first) and i < len(last) and first[i] ==last[i]:
#         i+=1
#     return first[:i]
# print(func(strs))
# print(func(strss))

# 实现冒泡排序

# def bubble_sort(arr):
#     n = len(arr)
#     # 遍历所有数组元素
#     for i in range(n):
#         #  创建一个标志，用于检查是否发生了交换
#         swapped = False
#         # 最后i个元素已经到位
#         for j in range(0,n-i-1):
#             # 遍历数组从0到n-i-1
#             # 交换如果元素发现大于下一个元素
#             if arr[j] > arr[j +1 ]:
#                 arr [j],arr[j+1] = arr[j + 1],arr[j]
#                 swapped = True
#
#         #  如果没有元素被交换，那么数组已经排序好了
#         if not swapped:
#             break
#
#     return arr
#
# arr = [52,14,23,85,64,12]
# bubble_sort(arr)
# print("排序后的数组是:",arr)


#  实现快速排序
def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]  # 选择中间的元素作为基准值，也可以随机选择
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)


# 测试快速排序
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quicksort(arr)
print("排序后的数组是：", sorted_arr)
